public class OddEvenList {

    public ListNode oddEvenList1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode temp = head;
        ListNode end = null;
        int len = 0;
        while (temp != null) {
            ++len;
            end = temp;
            temp = temp.next;
        }
        if (len % 2 == 0) {
            end.next = new ListNode();
            end = end.next;
        }
        int count = 0;
        ListNode l = head;
        ListNode r = head.next;
        while (count < len / 2) {
            if (count == len / 2 - 1) temp = l;
            ++count;
            l.next = r.next;
            l = l.next;
            end.next = r;
            end = end.next;
            r = l.next;
        }
        end.next = null;
        if (len % 2 == 0)  temp.next = r;
        return head;
    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode temp = head.next.next;
        int count = 1;
        ListNode l = head;
        ListNode r = head.next;
        ListNode dummyR = r;
        while (temp != null) {
            if (count % 2 == 0) {
                r.next = temp;
                r = r.next;
            } else {
                l.next = temp;
                l = l.next;
            }
            count++;
            temp = temp.next;
        }
        l.next = dummyR;
        r.next = null;
        return head;
    }
}
